1. Field of the Invention
This invention relates generally to a method for editing digital maps using active contour techniques, and more particularly toward methods for preventing active contour misalignment during manipulation in situations where two closely spaced active contours represent portions of a shaped, real world object.
2. Related Art
It is known in some applications to use knowledge-driven active contours in connection with digital map creation and refinement. Active contours are used extensively for image and video segmentation as well as for tracking. They can be formulated in the framework of variational methods. The basic principle is to construct a partial differential equation (PDE) from an energy criterion, including usually both region and boundary functionals, by computing some variation of Euler-Lagrange equation. The PDE changes the shape of the current curve according to some velocity field which can be thought of as a descent direction of the energy criterion. So-called “closed” curve active contours are those which enclose an initial region, whereas “open” curves are more frequently associated with roads, lanes, and other features found often in digital maps. Through an optimization process, active curves (either closed or open) are driven toward the edges of an image through the minimization of a boundary integral of features depending on edges.
For example, U.S. Pat. No. 5,862,245 in the name of Renouard, et al., issued Jan. 19, 1999, discloses a method of extracting a contour in a digital map image using, in part, an active contour manipulation approach. Contour extraction is based on an iterative process of deforming an active contour (open in this case) using an energy minimizing function. These and other prior art methods rely on the input of an initial contour, i.e., a so-called seed contour, into the digital map near the contour to be extracted. This initial contour may be in the form of a polygonal trace which can be as simple as a line or curvilinear mark. The iterative process deforms the initial contour until it finds an equilibrium position corresponding to an energy minimum, the equilibrium position defining a part of the trace of the contour to be extracted.
In connection with digital map editing activities, the initial or seed contour(s) may be obtained or derived from probe data, or from a possibly spatially inaccurate existing digital map. Probe data inputs are obtained from low-cost positioning systems and handheld devices and mobile phones with integrated GPS functionality for the purpose of incrementally creating and/or updating digital maps. The input to be processed from such probe data consists of recorded GPS traces in the form of a standard ASCII stream, which is supported by most existing GPS devices. The output may be a trace line in the form of a directed graph with nodes and edges or links associated with travel time information. The probe data, which creates the nodes or probe positions at regular intervals, can be transmitted to a collection service or other map making or data analysis service via wireless (e.g., cellular) transmission, Internet uploads, or by other means.
FIG. 1 depicts an exemplary digital map, or section thereof, such as may be of the type utilized by the methods of this invention. A digital map of this type is shown including primary roadways which may comprise divided motorways or dual carriageways, together with a hierarchy of secondary and tertiary roads representing smaller and lower classed driving lanes. FIG. 2 shows an exemplary GPS-enabled navigation device 10 including a display screen 12 or graphic user interface that portrays a network of streets for the purpose of rendering navigation assistance. The streets, of course, are provided by the digital map and correspond to a region of land in reality. The streets and roads depicted therein are contained in the digital map database as network elements which, of course, correspond to roads and lanes in real life.
It is often desirable or necessary to assess the accuracy of a digital map based on some new data set. The new data set may comprise the probe trace data mentioned earlier, a secondary digital map, a spatially unreliable digital map, or other type of reference information. Sometimes, it is desirable to assess the accuracy of probe data based on a new data set which actually comes from an existing digital map. FIGS. 4A-C demonstrate one way in which a new data set in the form of collected probe traces may be used as source geometry to provide an initial or seed contour for the purpose of realigning network elements in a digital map using an active contours approach. In these views, a network element 14 is shown representing a roadway having a sharp, 90 degree turn in real life along the length thereof. Probe traces collected over time and grouped according to the particular network element 14 are shown superimposed. Using well known mathematical techniques, the probe traces can be derived into a source geometry which forms an active contour 16 as shown in FIG. 4B, representing the initial or seed contour as may be used in an active contour manipulation exercise.
As mentioned above, as well known in the field, an active contour 16 gets assigned both internal and external energies. The internal energy of an active contour 16 is only determined by the shape of the active contour(s) itself and is completely independent from any external source (in the example given earlier the network segment 14). The so-called external energy assigned to the active contour 16 is determined by the external source. That external source itself is not assigned any energy: it merely serves as the source to create the velocity field. The external energy of the active contour 16 is then determined by how this active contour 16 is located in the velocity field, defined by the external source (in most implementations this is the sum of all the velocity field values at the locations of the active contour control points). Consequently, in this example the network element 14 determines the velocity field which in turn determines the external energy of the active contour 16.
An active contour manipulation strategy seeks to reposition the active contour 16 relative to the network element 14 by iteratively adjusting it to more desired positions by trying to lower the internal energy of the active contour 16 and to lower its external energy (which is—via the velocity field—determined by network element 14). These techniques, which have been perfected over time and are extraordinarily effective, can result in the fitting of the open-type active contour 16 to the network element 14 as shown in FIG. 4C. Thus, through application of well known active contour processes, the initial active contour 16 can be nicely fit to the network element 14. From there, further analysis and editing steps may be pursued, including the potential realignment of the network element 14 or the addition of new network elements, to name but a few. In the preceding example, a probe line (derived from probe data some way or another) is the source geometry used to create the initial contour, which is repositioned in a velocity field determined by a network element 16. It could also be the other way around: a network element 16 could be the source geometry used as an initial contour that is repositioned in a velocity field determined by probe data (some another external energy source). Naturally, both techniques represent equally valid and possible implementations of this concept.
A particular issue arises when the new data set produces one or more active contours which are spaced relatively close to one another and form a particular shape. This issue may for example arise when two nearby open active contours form respective portions of some fixed-shape object in reality, or when one closed active contour forms a particular geometry by itself. For example, as shown in FIG. 5A, first 18 and second 20 active contours may correspond to a network element 22 which comprises a generally north-south running motorway of the divided or dual-carriageway type. The first 18 and second 20 active contours represent traffic flowing in respective lanes, which active contours 18, 20 may have been derived from probe data. Likewise, third 24 and fourth 26 active contours correspond with a generally east-west running network element 28. The active contours 18, 20, 24, 26 are presented in somewhat raw or unprocessed format, that is prior to being optimized relative to the digital map. As can be seen quite clearly in FIG. 5A, a particularly prominent parallel relationship is established between the first and second 18, 20 and also between the third and fourth 24, 26 active contours. The parallel relationships in this example represent the respective portions of a fixed-shape object in reality, i.e., dual-carriageway highways.
Using conventional optimization techniques, each active contour 18, 20, 24, 26 is individually and separately optimized which, in this particular field, frequently results in bad alignments. For example, FIG. 5B shows the unintended and undesirable merging or collapsing of the first 18 and second 20 active contours over a portion of the network element 22 as a result of traditional optimization steps. Likewise, the third 24 and fourth 26 active contours have collapsed or merged together over a section of the east-west network element 28. Such results are generally undesirable and result in a loss of detail, increase in editorial efforts and quite often the necessity to intervene manually in the active contour process so as to assist in maintaining certain relative shapes between closely-spaced active contours. Similar misalignment scenarios can present in other situations as well. For example, one or more active contours occurring in the area of a roundabout, i.e., a driving circle, may also fall prey to poor alignment during the optimization process and require manual intervention to remediate the unintended consequences.
These shortcomings in the optimization process of active contours occur equally whether the new data set, which is treated as the source geometry to which an active contour is fitted, is probe data or an existing digital map. Accordingly, there is a need in the art for an improved method for realigning network elements in a digital map using active contour manipulation techniques so that certain desirable contours and/or shapes can be maintained during the optimization process.